The testing of ICs has evolved into a highly developed area of technology. Generally such testing may be implemented through the use of external test equipment, Built-in Self-Test (BIST) circuitry, or a combination of the two. Typically, all test methodologies involve applying a test pattern to the primary inputs (pins or scannable memory elements) of an IC, capturing the test response at the primary outputs (pins or scannable memory elements) and then comparing the captured data with predetermined values to determine whether the circuit has performed according to design. Automatic test pattern generation (ATPG) tools are used for testing digital circuits after the circuits have been manufactured. In general, an ATPG tool generates a set of test patterns that are applied to a circuit under test. The output of the circuit is analyzed to identify logic faults in the circuit design (i.e., “functional testing”), as well as detecting fabrication defects (i.e., “structural testing”).
ATPG tools are used to generate transition tests to detect delay defects in ICs. A transition fault in an IC refers to a circuit node (input, output, or internal node) that is slow to transition to the correct value. In general, some applications of transition fault test generation algorithms propagate transitions through the shortest circuit paths of the IC-under-test. The use of the shortest circuit paths simplifies the test generation by reducing the number and complexity of circuit paths tested. This method, however, reduces the likelihood of catching certain circuit defects, e.g., small delay defects, because the smaller delay defects may not manifest on the tested shorter circuit paths. To remedy this, in other applications, test generation algorithms focus on the longest paths for test generation. This method, unfortunately, becomes very complex and often takes far too long if only the longest paths are selected. In yet other applications, test algorithms rely on randomly chosen paths for test generation. This method, however, may not effectively catch some defects because the same path may be chosen every time. Accordingly, a new test generation algorithm is needed to exercise an increased number of original circuit paths during test generation in a more orderly manner.